import javax.swing.tree.TreeNode;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 28463
 * Date: 2022—07—13
 * Time: 9:02
 */
public class Demo01 {
/*    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null || p == null || q == null) {
                return null;
            }
            Stack<TreeNode> stack1 = new Stack<>();
            getPath(root,p,stack1);

            Stack<TreeNode> stack2 = new Stack<>();
            getPath(root,q,stack2);

            int size1 = stack1.size();
            int size2 = stack2.size();
            //两个栈个数一样
            if(size1 > size2) {
                int tmp = size1 - size2;
                while(tmp != 0) {
                    stack1.pop();
                    tmp--;
                }
            }else {
                int tmp = size2 - size1;
                while(tmp != 0) {
                    stack2.pop();
                    tmp--;
                }
            }
            //两个栈个数一样
            while(!stack1.empty() && !stack2.empty()) {
                if(stack1.peek() == stack2.peek()) {
                    return stack1.peek();
                }else {
                    stack1.pop();
                    stack2.pop();
                }
            }
            return null;//没有公共祖先
        }
        //找到根节点到指定节点路径上所有结点，放在栈中
        private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
            if(root == null || node == null) {
                return false;
            }
            stack.push(root);
            if(root == node) {
                return true;
            }
            boolean ret1 = getPath(root.left,node,stack);
            //只能说明左边没有node
            if(ret1 == true) {
                return true;
            }
            boolean ret2 = getPath(root.right,node,stack);
            if(ret2) {
                return true;
            }
            //根节点不是   根左不是  根右也不是
            stack.pop();
            return false;
        }
    }
    public class Solution {
        TreeNode prev = null;
        public void ConvertChild(TreeNode root) {
            if(root == null) return;

            ConvertChild(root.left);
            root.left = prev;
            if(prev != null) {
                prev.right = root;
            }
            prev = root;
            //System.out.print(root.val + " ");
            ConvertChild(root.right);
        }
        public TreeNode Convert(TreeNode pRootOfTree) {
            if(pRootOfTree == null) {
                return null;
            }
            ConvertChild(pRootOfTree);
            TreeNode head = pRootOfTree;
            while(head.left != null) {
                head = head.left;
            }
            return head;
        }
    }*/
}
